package com.test.demo;


import java.util.Arrays;

/**
 * Create by lu.jiang
 * Date 2021/4/16 10:56
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {3,2,1,7,4,6,5};
        sort(arr);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }

    private static void buildBigHeap(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            compare(arr, i);
        }
    }

    private static void compare(int[] arr, int i) {
        int parent;
        if (i % 2 == 1) {
            parent = (i - 1) / 2;
        } else {
            parent = (i - 2) / 2;
        }
        if (arr[i] > arr[parent]) {
            swap(arr, i, parent);
        }
        if (parent > 0) {
            compare(arr, parent);
        }
    }

    private static void swap(int[] arr, int i, int l) {
        int tmp = arr[i];
        arr[i] = arr[l];
        arr[l] = tmp;
    }

    private static void sort(int[] arr) {
        buildBigHeap(arr);
        for (int i = arr.length - 1; i >= 1; i--) {
            swap(arr, 0, i);
            adjust(arr, i - 1);
        }
    }

    private static void adjust(int[] arr, int end) {
        down(arr, 0, end);
    }

    private static void down(int[] arr, int i, int end) {
        int parent = i;
        boolean swapped = false;
        int nextParent = -1;
        int left = parent * 2 + 1;
        int right = parent * 2 + 2;
        if (left <= end && arr[parent] < arr[left]) {
            swap(arr, parent, left);
            swapped = true;
            nextParent = left;
        }
        if (right <= end && arr[parent] < arr[right]) {
            swap(arr, parent, right);
            if (!swapped) {
                swapped = true;
                nextParent = right;
            }
        }
        if (swapped) {
            down(arr, nextParent, end);
        }
    }

    private static int maxIndex(int[] arr, int i, int j, int end) {
        if (arr[i] >= arr[j] || end == 1) {
            return i;
        } else {
            return j;
        }
    }

}
